package com.demo.java.OD201_250.OD212;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

/**
 * @author bug菌
 * @Source 公众号：猿圈奇妙屋
 * @des： 【机器人活动区域】问题
 * @url： https://blog.csdn.net/weixin_43970743/article/details/145910047
 */
public class OdMain {
    // 定义四个方向：上、下、左、右
    private static final int[][] DIRECTIONS = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 读取矩阵的行数和列数
        int m = scanner.nextInt();
        int n = scanner.nextInt();

        // 构建矩阵
        int[][] matrix = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                matrix[i][j] = scanner.nextInt();
            }
        }

        // 计算最大活动区域
        System.out.println(maxActivityArea(matrix, m, n));

        // 关闭Scanner
        scanner.close();
    }

    // 计算最大活动区域
    private static int maxActivityArea(int[][] matrix, int m, int n) {
        boolean[][] visited = new boolean[m][n]; // 标记访问过的点
        int maxArea = 1; // 最小活动区域为1

        // 遍历每个点进行BFS
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (!visited[i][j]) {  // 如果这个点未被访问
                    maxArea = Math.max(maxArea, bfs(matrix, visited, i, j, m, n));
                }
            }
        }

        return maxArea;
    }

    // 使用BFS算法计算从(i, j)开始的活动区域大小
    private static int bfs(int[][] matrix, boolean[][] visited, int x, int y, int m, int n) {
        int area = 1; // 当前区域至少包含起始点
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{x, y});
        visited[x][y] = true;

        // BFS遍历
        while (!queue.isEmpty()) {
            int[] current = queue.poll();
            for (int[] direction : DIRECTIONS) {
                int newX = current[0] + direction[0], newY = current[1] + direction[1];

                // 确保不越界且符合条件
                if (newX >= 0 && newX < m && newY >= 0 && newY < n && !visited[newX][newY]
                        && Math.abs(matrix[current[0]][current[1]] - matrix[newX][newY]) <= 1) {
                    queue.offer(new int[]{newX, newY});
                    visited[newX][newY] = true;
                    area++; // 每次找到一个新的点，活动区域增加
                }
            }
        }

        return area;
    }
}